package edu.cmu.vlis.datamining.TopologicalFeatures;
import java.io.*;
import java.util.*;

public class Cascade {
	CascadeNode root;
	ArrayList<CascadeNode> nodes;


	public Cascade(String line) {
		this.nodes = new ArrayList<CascadeNode>();

		String[] parts = line.split(" ");
		//System.out.println(line);
		if (parts.length>1) {
			for (int i = 0; i < parts.length; i=i+2) {
				String fromnode = parts[i];
				String tonode = parts[i+1];
				addEdge(fromnode,tonode);
			}
			this.root = findRoot();
		}
		else {


			CascadeNode rootnode = makeNode(line);
			nodes.add(rootnode);
			this.root = rootnode;
		}
		//	print();
		//	System.out.println(line);
		//System.out.println(this.nodes.size());
	}


	public Cascade(String line, int k) {
		// this means you just grab the nodes and don't bother building nothin.
		this.nodes = new ArrayList<CascadeNode>();

		String[] parts = line.split(" ");
		if (parts.length>1) {
			for (int i = 0; i < parts.length; i=i+2) {
				String fromnode = parts[i];
				String tonode = parts[i+1];
				addTwoNodes(fromnode,tonode);
			}

		}
		else {
			CascadeNode rootnode = makeNode(line);
			nodes.add(rootnode);

		}
	}

	public ArrayList<Integer> getRoots() {
		ArrayList<Integer> roots = new ArrayList<Integer>();
		for (int i = 0; i < this.nodes.size(); i++) {
			if (nodes.get(i).isOrphan()) {
				roots.add(nodes.get(i).id);
			}
		}
		return roots;

	}


	public int size() {
		return this.nodes.size();
	}


	public String getEdges() {
		String str = "";
		if (nodes.size()==1) {
			str = str + nodes.get(0).id+";\n";
		}
		else{
			for (int i = 0; i < nodes.size(); i++) {
				CascadeNode cn = nodes.get(i);
				if (!cn.isOrphan()) {
					for (int p = 0; p < cn.parents.size(); p++) {
						int parentid = cn.parents.get(p).id;
						str = str + cn.id+"->"+parentid+" ; ";
					}
				}
			}
		}
		return str;
	}

	public void printEdges() {
		if (nodes.size()==1) {
			CascadeNode cn = nodes.get(0);
			//System.out.println(cn.id+";\n");
		}
		else {
			for (int i = 0; i < nodes.size(); i++) {
				CascadeNode cn = nodes.get(i);
				if (!cn.isOrphan()) {
					for (int p = 0; p < cn.parents.size(); p++) {
						int parentid = cn.parents.get(p).id;
						//System.out.print(cn.id+"->"+parentid+" ; ");
					}
				}
			}
			// System.out.println();
		}
	}

	public void remapToGeneric() {

		HashMap<Integer,Integer> idmap = new HashMap<Integer,Integer>();
		int currid = 0;
		for (int i = 0; i < nodes.size(); i++) {
			if (!idmap.containsKey(nodes.get(i).id)) {
				idmap.put(nodes.get(i).id,++currid);
			}
		}
		for (int i = 0; i < nodes.size(); i++) {
			int newcolor = idmap.get(nodes.get(i).id);
			nodes.get(i).id=newcolor;
		}


	}

	public void printEdgesParseFriendly() {
		for (int i = 0; i < nodes.size(); i++) {
			CascadeNode cn = nodes.get(i);
			if (!cn.isOrphan()) {
				for (int p = 0; p < cn.parents.size(); p++) {
					int parentid = cn.parents.get(p).id;
					//System.out.print(cn.id+":"+" "+parentid+":"+" ");
				}
			}
		}
		System.out.println();
	}

	private CascadeNode makeNode(String nodestring) {
		int id;
		nodestring = nodestring.trim();
		id = new Integer(nodestring);
		CascadeNode found = getNode(id);
		if (found!=null) {

			return found;
		}
		else    
			return new CascadeNode(id);
	}

	private int calculateConversationMass() {
		root.calculateConversationMass();
		return this.root.conversationMass;
	}

	private CascadeNode getNode(int id) {
		for (int i = 0; i < this.nodes.size(); i++) {
			CascadeNode curr = this.nodes.get(i);
			if (curr.id==id) {
				return curr;
			}
		}
		return null;
	}


	private void addTwoNodes(String fromnodestring, String tonodestring) {
		CascadeNode fromnode;
		CascadeNode tonode;

		CascadeNode tempfrom = makeNode(fromnodestring);
		CascadeNode tempto = makeNode(tonodestring);


		int fromid = tempfrom.id;
		int toid = tempto.id;

		fromnode = getNode(fromid);
		if (fromnode==null) {
			nodes.add(tempfrom);
			fromnode=tempfrom;
		}
		tonode = getNode(toid);
		if (tonode==null) {
			nodes.add(tempto);
			tonode=tempto;
		}

	}

	private void addEdge(String fromnodestring, String tonodestring) {

		CascadeNode fromnode;
		CascadeNode tonode;

		CascadeNode tempfrom = makeNode(fromnodestring);
		CascadeNode tempto = makeNode(tonodestring);

		int fromid = tempfrom.id;
		int toid = tempto.id;

		fromnode = getNode(fromid);
		if (fromnode==null) {
			nodes.add(tempfrom);
			fromnode=tempfrom;
		}
		tonode = getNode(toid);
		if (tonode==null) {
			nodes.add(tempto);
			tonode=tempto;
		}
		if (fromid != toid) {
			fromnode.setParent(tonode);
			tonode.addChild(fromnode);
		}
	}


	private CascadeNode findRoot() {
		int rootindex = -1;
		int roots = 0;
		for (int i = 0; i < this.nodes.size(); i++) {
			if (nodes.get(i).isOrphan()) {
				roots++;
				rootindex = i;
			}
		}
		if (roots>1) {
			// System.out.println("Oh crap more than one root");
			printEdges();
		}
		if (roots ==0) {
			//System.out.println("Oh crap no roots");
			printEdges();
			return null;
		}
		else
			return nodes.get(rootindex);
	}


	// CASCADE ISOMORPHISM METHODS

	/* say whether two cascades (rooted trees) are isomorphic
       modified to allow for nodes to have multiple parents (possibly in different levels)
       Modifications include:
         - Make sure no repeats of nodes inside level and between levels-- we want each one at lowest possible level.
         - Label nodes by level: l1v0, for instance
	 */

	public static boolean isomorphic(Cascade c1, Cascade c2) {
		//obviously if diff number of nodes, not iso
		if (c1.nodes.size()!=c2.nodes.size())
			return false;

		// we're going to want to clear out all pre-made labels
		//assert(c1.nodes.size()==c2.nodes.size());
		for (int i = 0; i < c1.nodes.size(); i++) {
			c1.nodes.get(i).label=" ";
			c2.nodes.get(i).label=" ";
		}
		// now get all levels
		ArrayList<ArrayList<CascadeNode>> allLevels1 = new ArrayList<ArrayList<CascadeNode>>();
		ArrayList<ArrayList<CascadeNode>> allLevels2 = new ArrayList<ArrayList<CascadeNode>>();

		boolean levelCheck = putNodesIntoLevels( c1, c2, allLevels1, allLevels2);
		if (!levelCheck) 
			return false;

		// now allLevels 1 and 2 contain each level of nodes.
		// thanks to modification, each node appears only on one level.


		int level=0;
		while (allLevels1.size() > 0 && allLevels2.size() > 0) {
			ArrayList<CascadeNode> currLevel1 = allLevels1.remove(allLevels1.size()-1);
			ArrayList<CascadeNode> currLevel2 = allLevels2.remove(allLevels2.size()-1);

			// we should have caught any with different numbers of nodes per level
			assert(currLevel1.size()==currLevel2.size());

			longLabelLevel(currLevel1);
			longLabelLevel(currLevel2);

			// now sort node labels

			boolean labelCheck = relabelLevel(currLevel1, currLevel2, level);
			if (!labelCheck)
				return false;
			level++;
		}

		// now we should be done.  If we're here we are isomorphic. 
		return true;
	}

	private static boolean putNodesIntoLevels(Cascade c1, Cascade c2, ArrayList<ArrayList<CascadeNode>> allLevels1, ArrayList<ArrayList<CascadeNode>> allLevels2) {
		ArrayList<CascadeNode> currLevel1 = new ArrayList<CascadeNode>();
		ArrayList<CascadeNode> children1 = new ArrayList<CascadeNode>();
		children1.add(c1.root);

		ArrayList<CascadeNode> currLevel2 = new ArrayList<CascadeNode>();
		ArrayList<CascadeNode> children2 = new ArrayList<CascadeNode>();
		children2.add(c2.root);

		while (children1.size()>0 || children2.size() > 0) {
			allLevels1.add(children1);
			allLevels2.add(children2);
			if (children1.size()!=children2.size())
				return false;
			currLevel1 = children1;
			currLevel2 = children2;
			children1 = new ArrayList<CascadeNode>();
			children2 = new ArrayList<CascadeNode>();
			if(currLevel1!=null ) {
				for (int i = 0; i < currLevel1.size(); i++) {
					if(currLevel1.get(i)!=null) {	
						for (int j = 0; j < currLevel1.get(i).children.size(); j++) {
							children1.add(currLevel1.get(i).children.get(j));
						}
					}
				}
			}
			if(currLevel2!=null ) {
				for (int i = 0; i < currLevel2.size(); i++) {
					if(currLevel2.get(i).children!=null) {	
						for (int j = 0; j < currLevel2.get(i).children.size(); j++) {
							children2.add(currLevel2.get(i).children.get(j));
						}
					}
				}
			}
		}
		//postcondition-- each level should have same number of nodes, same number of levels for each.

		//now go through levels and remove any repeats, starting at bottom.
		HashSet<CascadeNode> placed1 = new HashSet<CascadeNode>();
		HashSet<CascadeNode> placed2 = new HashSet<CascadeNode>();
		for (int l = allLevels1.size()-1; l>=0; l--) {
			currLevel1 = allLevels1.get(l);
			currLevel2 = allLevels2.get(l);
			ArrayList<CascadeNode> newLevel1 = new ArrayList<CascadeNode>();
			ArrayList<CascadeNode> newLevel2 = new ArrayList<CascadeNode>();
			for (int i = 0; i < currLevel1.size(); i++) {
				CascadeNode cn1 = currLevel1.get(i);
				if (!placed1.contains(cn1)) {
					newLevel1.add(cn1);
					placed1.add(cn1);
				}

				CascadeNode cn2 = currLevel2.get(i);
				if (!placed2.contains(cn2)) {
					newLevel2.add(cn2);
					placed2.add(cn2);
				}
			}


			//first we gotta make sure we removed the same number from both
			if (newLevel1.size()!=newLevel2.size()) {
				return false;
			}

			if (currLevel1.size()!=newLevel1.size()) {
				allLevels1.remove(l);
				allLevels1.add(l,newLevel1);

				//we don't need a separate test for 2 since we already know c1=c2 and n1=n2 and c1!=n1
				allLevels2.remove(l);
				allLevels2.add(l,newLevel2);

			}
			// okay, we're derefencing, just seems easiest.

			//just to be safe, count nodes.
			int oldsize=c1.size();
			int newcount = 0;
			for (int lev = 0; lev < allLevels1.size(); lev++) {
				newcount+=allLevels1.get(lev).size();
			}
			assert(oldsize==newcount);
		} 
		return true;
	}



	private static void longLabelLevel(ArrayList<CascadeNode> currLevel) {
		for (int i = 0; i < currLevel.size(); i++) {
			CascadeNode curr = currLevel.get(i);
			//only relakbel this one if there's no label already (from lower level)
            if(curr!=null) {
			String[] labels = new String[curr.children.size()];
			for (int j = 0; j < curr.children.size(); j++)
				labels[j]= curr.children.get(j).label;
			java.util.Arrays.sort(labels);
			for (int j = 0; j < labels.length; j++)
				curr.label=curr.label+labels[j];

		  }
		}
	}





	private static boolean relabelLevel(ArrayList<CascadeNode> currLevel1, ArrayList<CascadeNode> currLevel2, int level) {
		String[] labels1 = new String[0],labels2 = new String[0];
		
		labels1 = new String[currLevel1.size()];
		for (int i = 0; i < labels1.length; i++) {
			labels1[i] = currLevel1.get(i).label;
		}
		labels2 = new String[currLevel2.size()];
		for (int i = 0; i < labels2.length; i++) {
			labels2[i] = currLevel2.get(i).label;
		}

		java.util.Arrays.sort(labels1);
		java.util.Arrays.sort(labels2);


		//re-label, checking to see if they've got the same ones.
		int nindex = 0;
		String prevlabel=" ";
		HashMap<String,Integer> labelIndex = new HashMap<String,Integer>();
		labelIndex.put(prevlabel,nindex);
		for (int i = 0; i < labels1.length; i++) {
			String l1 = labels1[i];
			String l2 = labels2[i];
			if (l1.compareTo(l2)!=0)
				return false;
			if (l1.compareTo(prevlabel)!=0) {
				labelIndex.put(l1,++nindex);
				prevlabel=l1;
			}
		}

		for (int i = 0; i < currLevel1.size(); i++) {
			int myindex = labelIndex.get(currLevel1.get(i).label);
			currLevel1.get(i).label="l"+level+"v"+myindex;
		}
		for (int i = 0; i < currLevel2.size(); i++) {
			int myindex = labelIndex.get(currLevel2.get(i).label);
			currLevel2.get(i).label="l"+level+"v"+myindex;
		}
		return true;
	}



	// INNER CLASS


	private class CascadeNode {
		ArrayList<CascadeNode> parents; //modification to allow mult parents
		int id;
		int conversationMass;
		int level=0;
		int leafnum=0;
		ArrayList<CascadeNode> children;
		String label;

		CascadeNode(int id) {
			this.id = id;
			this.parents = new ArrayList<CascadeNode>();
			this.children = new ArrayList<CascadeNode>();
			this.conversationMass =0;
		}	
		private void setParent(CascadeNode parent) {
			this.parents.add(parent);
			//this.parent = parent;
		}
		private void addChild(CascadeNode child) {
			this.children.add(child);
		}
		int calculateConversationMass() {
			if (this.conversationMass == 0) {
				int cm = 1;
				for (int i = 0; i < children.size(); i++) {
					cm+=children.get(i).calculateConversationMass();
				}
				this.conversationMass = cm;
				return this.conversationMass;
			}
			else
				return this.conversationMass;
		}

		boolean isOrphan() {
			return parents.size()==0;
		}

		boolean isLeaf() {
			return children.size()==0;
		}

	}



}